package com.code.test.dance;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode.cn/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/description/
 * <p>
 * 螺旋遍历二维数组
 * <p>
 * 顺时针打印矩阵日志
 * <p>
 * 给定一个二维数组 array，请返回「螺旋遍历」该数组的结果。
 * <p>
 * 螺旋遍历：从左上角开始，按照 向右、向下、向左、向上 的顺序 依次 提取元素，然后再进入内部一层重复相同的步骤，直到提取完所有元素
 */
public class ShunshihzenPrintMatrix {


    public static void main(String[] args) {
        int[][] matrix = {
                {1, 2, 3, 4, 5},
                {6, 7, 8, 9, 10},
                {11, 12, 13, 14, 15},
                {16, 17, 18, 19, 20}
        };
        System.out.println(printMatrix(matrix));
        List<Integer> ret = printMatrix2(matrix);
        System.out.println(ret);

    }

    public static ArrayList<Integer> printMatrix(int[][] matrix) {
        ArrayList<Integer> ret = new ArrayList<>();
        int r1 = 0, r2 = matrix.length - 1, c1 = 0, c2 = matrix[0].length - 1;
        while (r1 <= r2 && c1 <= c2) {
            // 上
            for (int i = c1; i <= c2; i++)
                ret.add(matrix[r1][i]);
            // 右
            for (int i = r1 + 1; i <= r2; i++)
                ret.add(matrix[i][c2]);
            if (r1 != r2)
                // 下
                for (int i = c2 - 1; i >= c1; i--)
                    ret.add(matrix[r2][i]);
            if (c1 != c2)
                // 左
                for (int i = r2 - 1; i > r1; i--)
                    ret.add(matrix[i][c1]);
            r1++;
            r2--;
            c1++;
            c2--;
        }
        return ret;
    }

    public static List<Integer> printMatrix2(int[][] matrix) {

        List<Integer> ret = new ArrayList<>();

        int startRow = 0;
        int row = matrix.length - 1;
        int startCol = 0;
        int col = matrix[0].length - 1;

        while (startRow <= row && startCol <= col) {
            //从左到右
            for (int i = startCol; i <= col; i++) {
                ret.add(matrix[startRow][i]);
            }
            /**
             * 遍历右边，从上到下
             * 从下一行开始，到row结束
             */
            for (int i = startRow + 1; i <= row; i++) {
                ret.add(matrix[i][col]);
            }

            //从右向左
//            if (startRow != row) {
            /**
             * 从col-1开始，因为上面已经遍历过col，到startCol
             */
            for (int j = col - 1; j >= startCol; j--) {
                ret.add(matrix[row][j]);
            }
//            }

//            if (startCol != col) {
            //从下往上，遍历左边
            /**
             * 从row-1行，因为上面已经比那里过row，不能=startRow,不然会重复遍历
             */
            for (int j = row - 1; j > startRow; j--) {
                ret.add(matrix[j][startCol]);
            }
//            }


            startRow++;
            row--;
            startCol++;
            col--;
        }
        return ret;
    }


}
